// 动态规划解决斐波那契数组

const dynFib = (n) => {
  if(n === 1 || n === 0) return 1
  const arr = new Array(n)
 
  arr[0] = 1 
  arr[1] = 1
  
  for(let i = 2; i < n; ++i) {
    arr[i] = arr[i - 1] + arr[i - 2]
  }

  return arr[n -1]
}

console.log(dynFib(5))
console.log(dynFib(50))
console.log(dynFib(500))

const dynFibNoArray = (n) => {
  let result = 1
  let mid = 1
  let pre = 1

  for(let i = 0; i < n; i++) {
    if(i === 0 || i === 1) continue
    result = mid + pre  
    mid = pre
    pre = result
  }

  return result
}

console.log(dynFibNoArray(5))
console.log(dynFibNoArray(50))
console.log(dynFibNoArray(500))
